package pat.toplevel;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * It is vitally important to have all the cities connected by highways in a war.
 * If a city is conquered by the enemy, all the highways from/toward that city will be closed.
 * To keep the rest of the cities connected, we must repair some highways with the minimum cost.
 * On the other hand, if losing a city will cost us too much to rebuild the connection, we must pay more attention to that city.
 *
 * Given the map of cities which have all the destroyed and remaining highways marked, you are supposed to point out the city to which we must pay the most attention.
 *
 * Input Specification:
 * Each input file contains one test case. Each case starts with a line containing 2 numbers N (≤500),
 * and M, which are the total number of cities, and the number of highways, respectively.
 * Then M lines follow, each describes a highway by 4 integers: City1 City2 Cost Status where City1 and City2 are the numbers of the cities the highway connects (the cities are numbered from 1 to N), Cost is the effort taken to repair that highway if necessary, and Status is either 0, meaning that highway is destroyed, or 1, meaning that highway is in use.
 *
 * Note: It is guaranteed that the whole country was connected before the war.
 *
 * Output Specification:
 * For each test case, just print in a line the city we must protest the most, that is, it will take us the maximum effort to rebuild the connection if that city is conquered by the enemy.
 *
 * In case there is more than one city to be printed, output them in increasing order of the city numbers, separated by one space,
 * but no extra space at the end of the line. In case there is no need to repair any highway at all, simply output 0.
 */
public interface BattleOverCities {
    /**
     * 给定一个连通图，去掉某一点相邻边，如果它还是连通的，则cost为0，如果不连通，寻找一个使其连通的最小代价cost，寻找去掉后cost最大的点，若所有点去掉后依然连通，则返回0
     * @param citiesNum         城市数量
     * @param highwayNum        公路数量
     * @param highways          公路详情
     * @return                  最重要城市
     */
    List<Integer> func1(int citiesNum, int highwayNum, int[][] highways);
}

class BattleOverCitiesImpl1 implements BattleOverCities{
    static final int DESTROYED = 0;
    static final int IN_USE = 1;
    /**
     * 给定一个连通图，去掉某一点相邻边，如果它还是连通的，则cost为0，如果不连通，寻找一个使其连通的最小代价cost，寻找去掉后cost最大的点，若所有点去掉后依然连通，则返回0
     * @param citiesNum         城市数量
     * @param highwayNum        公路数量
     * @param highways          公路详情
     * @return                  最重要城市
     */
    @Override
    public List<Integer> func1(int citiesNum, int highwayNum, int[][] highways) {
        int[][] map = new int[citiesNum + 1][citiesNum + 1];
        initMap(map, citiesNum, highwayNum, highways);



        return new ArrayList<>();
    }
    private void initMap(int[][] map, int citiesNum, int highwayNum, int[][] highways){
        for (int i = 0; i < citiesNum; i++) {
            Arrays.fill(map[i], Integer.MAX_VALUE);
        }
        for(int[] highway : highways){
            int arcHead = highway[0];
            int arcTail = highway[1];
            int cost = highway[2];
            int status = highway[3];
            if(status == DESTROYED){
                map[arcHead][arcTail] = -1 * cost;
                map[arcTail][arcHead] = -1 * cost;
            }else if(status == IN_USE) {
                map[arcHead][arcTail] = cost;
                map[arcTail][arcHead] = cost;
            }
        }
    }
}
